package DataStructure.tree.practice;

import DataStructure.tree.TreeNode;

import java.util.ArrayDeque;

/**
 * 230. 二叉搜索树中第K小的元素
 */
public class KthSmallest {

    public int kthSmallest(TreeNode root, int k) {
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        int i = 0;
        while (root != null || !deque.isEmpty()) {
            while (root != null) {
                deque.add(root);
                root = root.left;
            }
            root = deque.removeLast();
            if (++i == k) return root.val;
            root = root.right;
        }
        return -1;
    }
}
